Microprocessors perform computational tasks in a wide variety of applications. Improved processor performance is almost always desirable, to allow for faster operation and/or increased functionality through software changes. In common embedded applications, such as portable electronic devices, conserving power is also desirable.
Common modern processors employ a pipelined architecture, where sequential instructions, each having multiple execution steps, are overlapped in execution. For maximum performance, the instructions should flow continuously through the pipeline. Any situation that causes instructions to stall in the pipeline detrimentally affects performance. If instructions must be flushed from the pipeline and subsequently re-fetched, both performance and power consumption may suffer.
Commonly all real-world programs include conditional branch instructions, the actual branching behavior of which is commonly not known until the instruction is evaluated deep in the pipeline. To avoid a stall that may result from waiting for actual evaluation of the branch instruction, common modern processors employ some form of branch prediction, whereby the branching behavior of conditional branch instructions is predicted early in the pipeline. Based on the predicted branch evaluation, the processor speculatively fetches (prefetches) and executes instructions from a predicted address—either the branch target address (if the branch is predicted taken) or the next sequential address after the branch instruction (if the branch is predicted not taken). When the actual branch behavior is determined, if the branch was mispredicted, the speculatively fetched instructions must be flushed from the pipeline, and new instructions fetched from the correct next address. Prefeteching instructions in response to an erroneous branch prediction adversely impacts processor performance and power consumption. Consequently, improving the accuracy of branch prediction is desirable.
Known branch prediction techniques include both static and dynamic predictions. The likely behavior of some branch instructions can be statically predicted by a programmer and/or compiler. One example is an error checking routine. Common code executes properly, and errors are rare. Hence, the branch instruction implementing a “branch on error” function will evaluate “not taken” a very high percentage of the time. Such an instruction may include a static branch prediction bit in the op code, set by a programmer or compiler with knowledge of the common likely outcome of the branch condition.
Dynamic prediction is generally based on the branch evaluation history (and in some cases the branch prediction accuracy history) of the branch instruction being predicted and/or other branch instructions in the same code. Extensive analysis of actual code indicates that recent past branch evaluation patterns may be a good indicator of the evaluation of future branch instructions.
One known form of dynamic branch prediction, depicted in FIG. 1, utilizes a Branch History Register (BHR) 100 to store the past n branch evaluations. In a simple implementation, the BHR 30 comprises a shift register. The most recent branch evaluation result is shifted in (for example, a 1 indicating taken and a 0 indicating not taken), with the oldest past evaluation in the register being displaced. A processor may maintain a local BHR 100 for each branch instruction. Alternatively (or additionally), a BHR 100 may contain the recent past evaluations of all conditional branch instructions, sometimes known in the art as a global BHR, or GHR. As used herein, BHR refers to both local and global Branch History Registers.
As depicted in FIG. 1, the BHR 100 may index a Branch Predictor Table (BPT) 102, which again may be local or global. The BHR 100 may index the BPT 102 directly, or may be combined with other information, such as the Program Counter (PC) of the branch instruction in BPT index logic 104. Other inputs to the BPT index logic 104 may additionally be utilized. The BPT index logic 104 may concatenate the inputs (known in the art as gselect), XOR the inputs (gshare), perform a hash function, or combine or transform the inputs in a variety of ways.
As one example, the BPT 102 may comprise a plurality of saturation counters, the MSBs of which serve as bimodal branch predictors. For example, each table entry may comprise a 2-bit counter that assumes one of four states, each assigned a weighted prediction value, such as:
11—Strongly predicted taken
10—Weakly predicted taken
01—Weakly predicted not taken
00—Strongly predicted not taken
The counter increments each time a corresponding branch instruction evaluates “taken” and decrements each time the instruction evaluates “not taken.” The MSB of the counter is a bimodal branch predictor; it will predict a branch to be either taken or not taken, regardless of the strength or weight of the underlying prediction. A saturation counter reduces the prediction error of an infrequent branch evaluation direction. A branch that consistently evaluates one way will saturate the counter. An infrequent evaluation the other way will alter the counter value (and the strength of the prediction), but not the bimodal prediction value. Thus, an infrequent evaluation will only mispredict once, not twice. The table of saturation counters is an illustrative example only; in general, a BHT may index a table containing a variety of branch prediction mechanisms.
Regardless of the branch prediction mechanism employed in the BPT 102, the BHR 100—either alone or in combination with other information such as the branch instruction PC—indexes the BPT 102 to obtain branch predictions. By storing prior branch evaluations in the BHR 100 and using the evaluations in branch prediction, the branch instruction being predicted is correlated to past branch behavior—its own past behavior in the case of a local BHR 100 and the behavior of other branch instructions in the case of a global BHR 100. This correlation is the key to accurate branch predictions, at least in the case of highly repetitive code.
Note that FIG. 1 depicts branch evaluations being stored in the BHR 100—that is, the actual evaluation of a conditional branch instruction, which may only be known deep in the pipeline, such as in an execute pipe stage. While this is the ultimate result, in practice, common high performance processors store the predicted branch evaluation from the BPT 102 in the BHR 100, and correct the BHR 100 later as part of a misprediction recovery operation if the prediction turns out to be erroneous. The drawing figures do not reflect this implementation feature, for clarity.
A common code structure that may reduce the efficacy a branch predictor employing a BHR 100 is the loop. A loop ends with a conditional branch instruction that tests a loop-ending condition, such as whether an index variable that is incremented each time through the loop has reached a loop-ending value. If not, execution branches back to the beginning of the loop for another iteration, and another loop-ending conditional branch evaluation.
If the loop executes through a large number of iterations, the “taken” backwards branches of the loop-ending branch instruction partially or fully saturate the BHR 100. Where the number of loop iterations equals or exceeds the BHR 100 width, at the end of the loop an n-bit BHR will contain precisely n−1 ones (taken) followed by a single zero (not taken), corresponding to a long series of branch taken evaluations resulting from the loop iterations, and ending with a single not-taken branch evaluation when the loop terminates. This effectively destroys the efficacy of the BHR 100, as all correlations with prior branch evaluations (for either a local or global BHR 100) are lost. In this case, the BHR 100 will likely map to the same BPT 102 entry for a given branch instruction (depending on the other inputs to the BPT index logic 104), rather than to an entry containing a branch prediction that reflects the correlation of the branch instruction to prior branch evaluations.
Additionally, the saturated BHR 100 may increase aliasing in the BPT 102. That is, all branch instructions following loops with common iterations will map to the same BPT 102 entry, if the BHR 100 directly indexes the BPT 102. Even where the BHR 100 is combined with other information, the chance of aliasing is increased. This adversely impacts prediction accuracy not only for the branch instruction following the loop, but also for all of the branch instructions that alias to its entry in the BPT 102.
If the loop executes through fewer iterations than the width of the BHR 100, the BHR 100 is not saturated and some prior branch evaluation history is retained. However, the bits representing the prior branch evaluation history are displaced in the BHR 100 by numerous “taken” results of the loop-ending branch instruction. Particularly where the number of loop iterations varies, this has two deleterious effects on branch prediction. First, the branch instruction will map to a much larger number of entries in the BPT 102 to capture the same correlation with prior branch evaluations, requiring a larger BPT 102 to support the same accuracy for the same number of branch instructions than would be required without the loop-ending branch affecting the BHR 30. Second, the branch predictors in the BPT 102 will take longer to “train,” increasing the amount of code that must execute before the BPT 102 begins to provide accurate branch predictions.
Patent application Ser. No. 11/066,508, assigned to the assignee of the present application and incorporated herein by reference, proposes to suppress updating the BHR 100 for loop-ending branch instructions. This resolves most of the deleterious effects of BHR 100 saturation or partial saturation on branch prediction accuracy. However, it fails to capture and exploit correlations that may exist between loop behavior and subsequent branch evaluation.
In common applications, the evaluation of a branch instruction may be correlated to the number of iterations of a preceding loop. For example, a scientific program may capture data points in a loop and, following the loop, branch to a statistical analysis subroutine where the captured data is analyzed. However, if the loop iterates relatively few times, capturing few data points and yielding a small sample, statistical analysis may be unreliable, and may be skipped. In this case, the evaluation of the conditional instruction branching to the statistical analysis subroutine is strongly correlated to the number of iterations of the data acquisition loop.
In another example, an application may use a loop structure to search through a list, transaction log, history file, or similar data structure. If an item matching the search parameters appears frequently in the list, relatively few loop iterations will be required to locate the item. Consequently, an item appearing infrequently may require a large number of iterations through the search loop. The evaluation of a subsequent branch instruction may be correlated to the frequency with which a particular item appears in the list, and hence correlated to the number of loop iterations required to locate the item.
Suppressing the update of the BHR 100 in response to loop-ending branch instruction evaluations fails to capture any correlation between the number of loop iterations and the branch behavior of a subsequent branch instruction. On the other hand, maintaining a full history of the evaluations of the loop-ending branch instruction fully or partially saturates the BHR 100, losing the correlation to branch instruction evaluations prior to the loop.